On the importance of graph search algorithms for DRGEP-based mechanism reduction methods

摘要

The importance of graph search algorithm choice to the directed relationgraph with error propagation (DRGEP) method is studied by comparing basic andmodified depth-first search, basic and R-value-based breadth-first search(RBFS), and Dijkstra's algorithm. By using each algorithm with DRGEP to produceskeletal mechanisms from a detailed mechanism for n-heptane withrandomly-shuffled species order, it is demonstrated that only Dijkstra'salgorithm and RBFS produce results independent of species order. In addition,each algorithm is used with DRGEP to generate skeletal mechanisms for n-heptanecovering a comprehensive range of autoignition conditions for pressure,temperature, and equivalence ratio. Dijkstra's algorithm combined with acoefficient scaling approach is demonstrated to produce the most compactskeletal mechanism with a similar performance compared to larger skeletalmechanisms resulting from the other algorithms. The computational efficiency ofeach algorithm is also compared by applying the DRGEP method with each searchalgorithm on the large detailed mechanism for n-alkanes covering n-octane ton-hexadecane with 2115 species and 8157 reactions. Dijkstra's algorithmimplemented with a binary heap priority queue is demonstrated as the mostefficient method, with a CPU cost two orders of magnitude less than the othersearch algorithms.